package Other;

import java.util.*;

public class slidingWindow {
    //滑动窗口的问题
    public static class WindowMax{
        //黑盒,提供操作 L 和 R 和获取最大值的方法
        private int L;
        private int R;
        private int[] arr;
        private LinkedList<Integer> qmax;
        public WindowMax(int[] a){
            arr = a;
            L = -1;
            R = 0;
            qmax = new LinkedList<>();
        }
        public void addNumFromRight(){
            if (R == arr.length){
                return;
            }
            while (!qmax.isEmpty() &&arr[qmax.peekLast()] <= arr[R]){
                qmax.pollLast();
            }
            qmax.addLast(R);
            R++;
        }
        public void removeNumFromLeft(){
            if (L > R-1){
                return;
            }
            L++;
            if (qmax.peekFirst() == L){
                qmax.pollFirst();
            }
        }
        public Integer getMax(){
            if (!qmax.isEmpty()){
                return arr[qmax.pollFirst()];
            }
            return null;
        }
    }










    //    arr 是数组的值 , k 是窗口的大小
    public static int[] getMaxWindows(int[] arr,int k){
        if (arr == null || k < 1 || arr.length < k){
            return null;
        }
        //下标 值 由大到小
        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length];
        int index =0;

        for (int i = 0; i < arr.length; i++) {//窗口刚才的R
            // i -> arr[i]
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){//只要队列不为空 和 前面的数小于要进的数,就弹出
                qmax.peekLast();
            }
            qmax.addLast(i);
            //判断下标有没有过期
            if (qmax.peekFirst() == i - k){//过期的下标
                qmax.pollFirst();
            }
            //窗口形成了,就将最大值进入
            if (i > k-1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    // 1 滑动窗口 - 长度最小的子数组
    public static int minSubArrayLen(int target, int[] nums) {
        int left =0 ,right=0,sum=0;
        int len =Integer.MAX_VALUE;
       while (right< nums.length){
            sum +=nums[right];
            while (sum >= target){
               len = Math.min(len,right-left+1);
                sum -=nums[left++];
            }
           right++;
        }
        return len == Integer.MAX_VALUE?0:len;
    }

    public static int lengthOfLongestSubstring(String s) {

        int[] hash = new int[128];
        char[] chars = s.toCharArray();

        int ans =0;
        int left =0 ,right =0 ,n = chars.length;

       while (right < n){
           hash[chars[right]]++;

           while (hash[chars[right]] >1){
               hash[chars[left++]]--;
           }
           ans=Math.max(ans,right-left+1);
           right++;
       }
        return ans;
    }

    public static int longestOnes(int[] nums, int k) {
        int ans =0;
        int left =0 ,right=0,sum=0;
        while (right < nums.length){
            if (nums[right] == 0){
                sum++;
                while (sum > k ){
                    if (nums[left++] == 0)sum--;
                }
            }
            ans = Math.max(ans,right-left+1);
            right++;
        }
        return ans;
    }

    public int minOperations(int[] nums, int x) {
        int sum =0;
        for (int a:nums) {
            sum+=a;
        }
        int target = sum-x;
        if (target < 0)return -1;
        int ans =-1;
        for (int right = 0,left=0,tmp=0; right < nums.length ; right++) {
            tmp+=nums[right];
            while (tmp > target){
                tmp-=nums[left++];
            }
            if (tmp == target){
                ans = Math.max(ans,right-left+1);
            }
        }
        return ans == -1?-1: nums.length-ans;
    }
    public static int totalFruit(int[] fruits) {
        int left=0,right=0;
        HashMap<Integer,Integer> map = new HashMap<>();
        int ans =0;
        while (right < fruits.length){
           map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
            while (map.size()>2){

                map.put(fruits[left],map.get(fruits[left])-1);
                if (map.get(fruits[left])==0){
                    map.remove(fruits[left]);
                }
                left++;
            }
            ans = Math.max(ans,right-left+1);
            right++;
        }
        return ans;
    }

    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ans = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hs1 = new int[26];
        for (char ch:p) {
            hs1[ch-'a']++;
        }
        int[] hs2 = new int[26];
        for (int right = 0,left =0 ,count=0; right < s.length; right++) {
            char in = s[right];
            if (++hs2[in -'a'] <= hs1[in-'a'])count++;
            if (right-left+1>p.length){
                char out =s[left++];
                if ( hs2[out-'a']-- <= hs1[out-'a'])count--;
            }
            if (count == p.length)ans.add(left);
        }
        return ans;
    }
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        HashMap<String,Integer> h1 = new HashMap<>();

        // 将words中字符串都进入到哈希表1中
        for (String ret:words) {
            h1.put(ret,h1.getOrDefault(ret,0)+1);
        }
        //划分n次字符串 s,n = word中单词的长度
        // 对每一次划分完成的S 进行遍历,是上一题一样,看这个长度内的有效字符串是不是相等
        int len =words[0].length();
        for (int i = 0; i < len; i++) {
            int count =0;
            HashMap<String,Integer> h2 = new HashMap<>();
            for (int right = i,left=i;right+len<=s.length();right+=len) {
                // 进窗口加维护
                String ret = s.substring(right,right+len);
                h2.put(ret,h2.getOrDefault(ret,0)+1);
                if (h2.get(ret) <= h1.getOrDefault(ret,0))count++;

                if (right - left+1 > len* words.length){
                    String  out =   s.substring(left,left+len);
                    if (h2.get(out) <= h1.getOrDefault(out,0))count--;
                    h2.put(out,h2.get(out)-1);
                    left+=len;
                }
               if (count == words.length)ans.add(left);
            }
        }
        return ans;
    }
    public String minWindow(String s, String t) {
        String  ans ;
        int[] hash1 = new int[128];
        int kinds=0;// 字符串t有多少种
        for (Character c:t.toCharArray())if (hash1[c]++ == 0)kinds++;

        int minLen = Integer.MAX_VALUE;
        int begin = -1;
        int[] hash2 = new int[128];//统计窗口中频次
        for (int left=0,right=0,count=0;right<s.length();right++) {
            char k  = s.charAt(right);
            if (++hash2[k] == hash1[k])count++;// 进窗口+维护
            while (kinds == count){
                // 更新结果
                if (right-left+1 < minLen){
                    minLen = right-left+1;
                    begin = left;
                }
                char out = s.charAt(left++);
                if (hash2[out]-- == hash1[out])count--;
            }
        }
        return begin == -1 ? "":s.substring(begin,begin+minLen);
    }



}
